/*
 * quickSort.cpp
 *
 *  Created on: Sep 12, 2012
 *      Author: jeffrey
 */

#include<iostream>
#include<stdlib.h>
#include"../header/util.h"
using namespace std;
class QuickSort {
public:
	static void sort(int array[], int len) {
		quickSort(array, 0, len - 1);
	}
private:
	static void swap(int array[], int i, int j) {
		int tmp = array[i];
		array[i] = array[j];
		array[j] = tmp;
	}
	static int partition(int array[], int s, int e, int p) {
		int pValue = array[p];
		swap(array, p, e);
		int tmp = s;
		for (int i = s; i < e; i++) {
			if (array[i] < pValue)
				swap(array, tmp++, i);
		}
		swap(array, tmp, e);
		return tmp;
	}
	static void quickSort(int array[], int s, int e) {
		if (s < e) {
			int p = rand() % (e - s + 1)+s;
			int pos = partition(array, s, e, p);
			quickSort(array, s, pos - 1);
			quickSort(array, pos+1, e);
		}

	}

};
//int main() {
//	int a[]={3,5,1,-1,2,-9,0,0,9,-3,5,1};
//	QuickSort::sort(a,sizeof(a)/sizeof(int));
//	UtilFunc::printArray(a,sizeof(a)/sizeof(int));
//}
